class Node{
  constructor(key, left = null, right = null){
    this.key = key;
    this.left = left;
    this.right = right;
  }
}

Node.prototype.getNode = function(key) {
  return new Node(key);
}

function predesccessor(root){
  let temp = root.left;
  while(temp.right) temp = temp.right;
  return temp;
}

// 给root插入key节点，并返回root;
Node.prototype.insert = function(root, key) {
  if(!root) return this.getNode(key);
  if(key > root.key) root.right = this.insert(root.right, key);
  if(key < root.key) root.left = this.insert(root.left, key);
  return root;
}

// 从root删除key节点，并返回删除后的root
Node.prototype.erase = function(root, key) {
  if(!root) return root;
  if(key < root.key) {
    root.left = this.erase(root.left, key);
  } else if(key > root.key) {
    root.right = this.erase(root.right, key);
  } else {
    if(!root.left && !root.right) {
      delete root;
      return null;
    } else if(!root.left || !root.right) {
      let temp = root.left ? root.left : root.right;
      delete root;
      return temp;
    } else {
      let temp = predesccessor(root);
      root.key = temp.key;
      root.left = this.erase(root.left, temp.key);
    }
  }
  return root;
}


function output(root){
  let arr = [];

  function inner(root){
    if(!root) return;
    inner(root.left);
    arr.push(root.key);
    inner(root.right);
  }
  inner(root);

  console.log(arr.join(','));
}

function test() {
  let root = new Node(5);
  root.insert(root, 9);
  root.insert(root, 8);
  root.insert(root, 3);
  root.insert(root, 2);
  root.insert(root, 4);
  root.insert(root, 1);
  root = root.erase(root, 5);
  root.erase(root, 8);
  root.erase(root, 3);
  output(root);
}
test();